package Experiment;

import java.util.Scanner;

//操作系统作业银行家算法
public class Banker_Algorithm {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        //资源数
        int m=sc.nextInt();
        //进程数
        //带2的皆为预分配
        int[]Available=new int[n];
        int[]Available2=new int[n];
        //可利用资源
        int[][]Need=new int[m][n];

        //当前的最大需求
        int[][]Max=new int[m][n];
        //最大需求
        int[][]Allocation=new int[m][n];
        int[][]Allocation2=new int[m][n];
        //已分配资源
        int a=0;
        //判断输入值是否正常
        int[][]arr=new int[m][n];
        System.out.println("请输入可分配资源");
        for (int i = 0; i < n; i++) {
            Available[i]=sc.nextInt();

        }
        //预分配
        System.out.println("请输入预分配进程数");
        int x=sc.nextInt();
        //请求申请资源的进程号
        int[]Requesti=new int[n];
        //申请的资源量
        System.out.println("请输入预分配资源");
        for (int i = 0; i < n; i++) {
            Requesti[i]=sc.nextInt();
            if(Requesti[i]>Available[i]) {
                //判断申请资源是否大于可分配资源
                a = 1;
            }
        }
        System.out.println("请输入最大需求");
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Max[i][j]=sc.nextInt();
            }
        }System.out.println("请输入当前最大需求");
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Need[i][j]=sc.nextInt();
                arr[i][j]=Need[i][j];
            }
            if(x==i){
                for (int j = 0; j < n; j++) {
                    if(Requesti[j]>Need[i][j]) {
                        a = 1;
                    }

                }
            }
        }
        System.out.println("请输入已分配资源");
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                Allocation[i][j]=sc.nextInt();
                Allocation2[i][j]=Allocation[i][j];
            }
        }
        if(a==1){
            System.out.println("输入的资源申请不符合");
            return;
        }else{
            for (int i = 0; i < n; i++) {
                Available2[i]=Available[i]-Requesti[i];
                arr[x][i]=Need[x][i]-Requesti[i];
                Allocation2[x][i]=Allocation[x][i]+Requesti[i];
            }
        }
        String s=security(arr,Available2,Allocation2);
        if("-100".equals(s)){
            System.out.println("不可分配");
        }else {
            for (int i = 0; i < n; i++) {
                Need[x][i]=Need[x][i]-Requesti[i];
                Allocation[x][i]=Allocation[x][i]+Requesti[i];
            }


            System.out.println("安全序列为："+s);
        }


    }
    //检查是否为安全状态函数
    static String security(int[][]arr,int[]Available2,int[][]Allocation2){
        int num=0;
        //表示可分配资源数
        int sum=0;
        //已分配的进程数
        int temp=0;
        //不满足的资源数
        StringBuilder s=new StringBuilder();
        //安全序列
        int i=-1;
        while (true){
                i++;
            if(temp> arr.length){
                System.out.println(i);
                return "-100";
            }
                for (int j = 0; j < arr[i].length; j++) {
                    if(Available2[j]>=arr[i][j]&&arr[i][j]>=0){
                        num++;
                    }
                    else{
                        num=0;
                        temp++;
                        break;
                    }
                }
                if(num==arr[0].length){
                    for (int j = 0; j < arr[0].length; j++) {
                        Available2[j]=Allocation2[i][j]+Available2[j];
                        arr[i][j]=-1;
                        //资源分配已完成

                    } sum++;
                    temp=0;
                    num=0;
                    s.insert(s.length(),i);
                    i=-1;
                }



            if(sum==arr.length){
                return s.toString();
            }

        }
    }


}
